Algorithm Implementation/Sorting/Bubble sort

Bubble Sort

The bubble sort is also known as the ripple sort. The bubble sort is probably the first, reasonably complex module that any beginning programmer has to write. It is a very simple construct which introduces the student to the fundamentals of how sorting works.

A bubble sort makes use of an array and some sort of "swapping" mechanism. Most programming languages have a built-in function to swap elements of an array. Even if a swapping function does not exist, only a couple of extra lines of code are required to store one array element in a temporary field in order to swap a second element into its place. Then the first element is moved out of the temporary field and back into the array at the second element's position.

Why is it called a bubble sort?

The bubble sort gets its name because elements tend to move up into the correct order like bubbles rising to the surface.

C

  //Start sorting
  int i, j; //variables used for for loops.
  int temp; //used to swap values of two array entries
  for (i = 0; i < length; i++) {
    for (j = 0; j < length - 1; j++) {
      if (data[j] > data[j + 1]) {
        temp = data[j];
        data[j] = data[j + 1];
        data[j + 1] = temp;
      }
    }
  }

C#

 static void BubbleSort(IComparable[] data)
 {
     int i = data.Length - 1;
     while(i > 0)
     {
         int swap = 0;
         for (j = 0; j < i; j++)
         {
             if (data[j].CompareTo(data[j + 1]) > 0)
             {
                 temp = data[j];
                 data[j] = data[j + 1];
                 data[j + 1] = temp;
                 swap = j;
             }
         }
         i = swap;
     }
 }

Ada

 type Integer_array is Array (Natural range <>) of Integer;
 
 procedure Bubble_Sort (Data : in out Integer_Array) is
    Temp : Integer;
 begin
    for I in reverse Data'Range loop
       for J in Data'First .. I loop
          if Data(I) < Data(J) then
             Temp := Data(J);
             Data(J) := Data(I);
             Data(I) := Temp;
          end if;
       end loop;
    end loop;
 end Bubble_Sort;

APL

APL Implementation (not original APL, >>>>> try to find Iverson's original APL implementation <<<<<)

ASCII Character Set with comments:

[0] SV{<-}BubbleSort VEC;#IO;SMALLEST;WH

[1] @ This is a silly thing to do in APL but here it is for pedagogical purposes.

[2] @ Of course, what we re teaching here is a poor way to implement a poor

[3] @ algorithm. At least we reduce its loopiness a bit by some array ops.

[4] SV{<-}{iota}#IO{<-}0 @ Sorted Vector will be result.

[5] :While 0<{rho}VEC @ VECtor will get smaller as we remove each smallest.

[6] WH{<-}VEC=SMALLEST{<-}{min}/VEC @ SMALLEST numbers and WHere they are.

[7] SV{<-}SV,WH/VEC @ Put all occurences of smallest at end of result.

[8] VEC{<-}(~WH)/VEC @ Remove these from source vector.

[9] :EndWhile

APL Character Set:

[0] SV←BubbleSort VEC;#IO;SMALLEST;WH

[4] SV←ι#IO←0

[5] :While 0<ρVEC

[6] WH←VEC=SMALLEST←⊥/VEC

[7] SV←SV,WH/VEC

[8] VEC←(~WH)/VEC

[9] :EndWhile

J

Generally, this task should be accomplished in J using /:~. Here we take an approach that's more comparable with the other examples on this page.

bubbleSort=: (([ (<. , >.) {.@]) , }.@])/^:_

Test program:

?. 10 $ 10

4 6 8 6 5 8 6 6 6 9

bubbleSort ?. 10 $ 10

4 5 6 6 6 6 6 8 8 9

For the most part, bubble sort works against J's strengths. However, once a single pass has been implemented as a list operation, ^:_ tells J to repeat this until the result stops changing.

Assembly

MASM. Sorts an array data of DWORDS with length elements.

 bs proc array:DWORD,length:DWORD
        mov ecx,length
        mov edx,data
        outerloop:
        xor ebp,ebp
        innerloop:
        mov eax,DWORD PTR [edx+ebp*4+4]
        cmp DWORD PTR [edx+ebp*4],eax
        jb @F
        xchg eax,DWORD PTR [edx+ebp*4]
        mov DWORD PTR [edx+ebp*4+4],eax
        @@:
        add ebp,1
        cmp ebp,ecx
        jb innerloop
        loop outerloop
        pop ebp
        retn 8
 bs endp

BASIC

 Sub Bubblesort(Data() as Integer, Length as Integer)
    Dim I as Integer
    Dim J as Integer
    Dim Temp as Integer
 
    For I = Length -1 To 1 Step -1
       For J = 0 to I - 1
          IF Data(J)>Data(J+1) THEN  ' Compare neighboring elements
             Temp = Data(j) 
             Data(J) = Data(J+1)
             Data(J+1) = Temp
          End If
       Next J
    Next I
 
 End Sub

Common Lisp

(defun bubble-sort (data)
  (loop repeat (1- (length data)) do
    (loop for ls on data while (rest ls) do
      (when (> (first ls) (second ls))
        (rotatef (first ls) (second ls)))))
  data)

FORTRAN

      SUBROUTINE sort (data_x, data_y, length)
 Global Definitions
       REAL data_x(*)
       REAL data_y(*)
       INTEGER length
 Local
      REAL x_temp
      REAL y_temp      
      LOGICAL inorder      
      inorder = .false.
      do 90 while (inorder.eq..false.)
       inorder = .true.       
       do 91 i=1, length              
 Check Equilivant Points and swap those on Y
       if (data_x(i).eq.data_x(i+1) ) then
        if (data_y(i).lt.data_y(i+1) ) then
         x_temp = data_x(i)
         y_temp = data_y(i)
         data_x(i) = data_x(i+1)
         data_y(i) = data_y(i+1)
         data_x(i+1) = x_temp
         data_y(i+1) = y_temp
         inorder = .false.
        endif
       endif
 If x needs to be swapped, do so 
       if (data_x(i).lt.data_x(i+1) )then
        x_temp = data_x(i)
        y_temp = data_y(i)
        data_x(i) = data_x(i+1)
        data_y(i) = data_y(i+1)
        data_x(i+1) = x_temp
        data_y(i+1) = y_temp
        inorder = .false.
       endif 
 91    continue
 90    continue       
      END SUBROUTINE sort

Java

public static int[] bubblesort(int[] data) {
    boolean swapped = true;
    for(int i = data.length - 1; i > 0 && swapped; i--) {
        swapped = false;
        for (int j = 0; j < i; j++) {
            if (data[j] > data[j+1]) {
                int temp = data[j];
                data[j] = data[j+1];
                data[j+1] = temp;
                swapped = true;
            }
        }
    }
    return data;
}

JavaScript

JavaScript Implementation with simple HTML test page

<html>
<head>
<script type="text/javascript">
// GLOBAL FUNCTION
Array.prototype.bubble_sort = function() {
    var i, j;
    var data = this.slice(0);
    var swap = function(j, k) {
      var temp = data[j];
      data[j] = data[k];
      data[k] = temp;
      return(true);
    }
    var swapped = false;
    for(i=1; i<data.length; i++) {
      for(j=0; j<data.length - i; j++) {
        if (data[j+1] < data[j]) {
          swapped = swap(j, j+1);
        }
      }
      if (!swapped) break;
    }
    return(data)
}
 
// LOCAL FUNCTION
show = function (showdata, title) {
  document.writeln("<h4>"+title+":</h4>");
  document.writeln(showdata.join(", ")+"<br />");
} 
</script>
</head>
<body>
<script>
// MAIN
// test bubble_sort function
sorted_data = [1, 4, 7, 2, 1, 3, 2, 1, 4, 2, 3, 2, 1].bubble_sort();
show(sorted_data, "Sorted Data");
// result: [1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 4, 4, 7]
</script>
</body>
</html>

Pascal

 Procedure BubbleSort(var data:IntArray; length:integer);
  var i,j,temp: integer;
  begin
   for i:=1 to length-1 do
    for j:=1 to length do
     if data[i]>data[j] then
        begin
         temp:=data[i]; data[i]:=data[j]; data[j]:=temp;
        end;
  end;

Perl

 sub swap {
   @_[0, 1] = @_[1, 0];
 }
 
 sub bubble_sort {
   for ($i=$[; $i < $#_; ++$i) {
     for ($j=$[; $j < $#_; ++$j) {
       ($_[$j] > $ _[$j+1]) and swap($_[$j], $_[$j+1]);
     }
   }
 }

PHP

 function bubbleSort ($data) {
     $length = count($data);
     for ($i=0; $i<$length; $i++) {
          for ($j=0; $j<$length-1-$i; $j++) {
               if ($data[$j+1] < $data[$j]) {
                   Swap($data, $j, $j+1);
               }
          }
     }
     return $data;
 }
 function Swap (&$dat, $index1, $index2) {
     list($dat[$index1], $dat[$index2]) = array($dat[$index2], $dat[$index1]);
 }

Python

 def bubblesort(data):
     "Sorts data in place and returns it."
     for i in range(len(data)-1, 0, -1):
         for j in range(i):
             if data[j] > data[j + 1]:
                data[j], data[j + 1] = data[j + 1], data[j]
     return data

Ruby

module BubbleSort
  def self.sort(data)
    sort!(data.clone)
  end
 
  def self.sort!(data)
    0.upto(data.size-1) do |i|
      (data.size-1).downto(i+1) do |j|
        (data[j], data[j-1] = data[j-1], data[j]) if data[j] < data[j-1]
      end
    end
    data
  end
end

Scheme

 (define (bubblesort data)
  (define (swap-pass data)
    (if (eq? (length data) 1) 
        data
        (let ((fst (car data))(snd (cadr data))(rest (cddr data)))
          (if (> fst snd) 
              (cons snd (swap-pass (cons fst rest)))
              (cons fst (swap-pass (cons snd rest)))))))
  (let for ((times (length data))
            (val data))
    (if (> times 1)
        (for (- times 1)(swap-pass val))
        (swap-pass val))))

Visual Basic

  Public Sub BubbleSort(ByRef Data() As Long)
    Dim i, j    As Integer

    For i = UBound(Data) To 0 Step -1 
      For j = 0 To i - 1 
          If Data(j) > Data(j + 1) Then
              Call swap(Data(j), Data(j + 1))
          End If
      Next j
    Next i
  End Sub
 
  Private Sub swap(ByRef data1 As Long, ByRef data2 As Long)
    Dim temp As Long

    temp = data1
    data1 = data2
    data2 = temp
  End Sub

COBOL

For sorting a WORKING STORAGE table, the following example assumes that the table is already loaded. The literals "a" indicates the size of the row, and "b" how many rows in the table.

      WORKING-STORAGE SECTION.
     *
      01  WS-SORT-AREA.
          05  WS-SORT-TABLE.
              10  WS-SORT-ROW PIC X(a) OCCURS b.
          05  WS-TEMP-ROW     PIC X(a).
          05  WS-ROW-MAX      PIC S9(4) COMP VALUE b.
          05  WS-SORT-MAX     PIC S9(4) COMP.
          05  WS-SORT-UP      PIC S9(4) COMP.
          05  WS-SORT-DOWN    PIC S9(4) COMP.
          05  WS-SORT-INCR    PIC S9(4) COMP.
          05  WS-SORT-TEST    PIC S9(4) COMP.
     *
       PROCEDURE DIVISION.
     *
       MY-SORT SECTION.
       MY-SORT-START.
     *
     * find the last entry
     *
          PERFORM VARYING WS-SORT-MAX FROM WS-ROW-MAX BY -1
              UNTIL WS-SORT-MAX = ZERO
              OR    WS-SORT-ROW (WS-SORT-MAX) NOT = SPACES
          END-PERFORM.
     *
     * bubble sort into required sequence
     *
          PERFORM VARYING WS-SORT-UP FROM WS-SORT-MAX BY -1
              UNTIL WS-SORT-UP = ZERO
     *
              MOVE ZERO TO WS-SORT-TEST
     *
              PERFORM VARYING WS-SORT-DOWN FROM 1 BY 1
                  UNTIL WS-SORT-DOWN = WS-SORT-UP
     *
                  ADD 1 TO WS-SORT-DOWN GIVING WS-SORT-INCR
     *
                  IF  WS-SORT-ROW (W30-SORT-DOWN)
                    > WS-SORT-ROW (W30-SORT-INCR)
     *
                      MOVE WS-SORT-ROW (WS-SORT-DOWN)
                        TO WS-TEMP-ROW
                      MOVE WS-SORT-ROW (WS-SORT-INCR)
                        TO WS-SORT-ROW (WS-SORT-DOWN)
                      MOVE WS-TEMP-ROW
                        TO WS-SORT-ROW (WS-SORT-INCR)
                      ADD 1 TO WS-SORT-TEST
                  END-IF
              END-PERFORM
     *
              IF  WS-SORT-TEST = ZERO
                  NEXT SENTENCE
              END-IF
          END-PERFORM.
     *
      MY-SORT-EXIT.
          EXIT.}}